/**
 * 给你由整数组成的山脉数组 arr 
 * 返回任何满足 arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1] 的下标 i 。
 **/
#include<iostream>
#include<vector>
using namespace std;

/**
 * Solution 1:二分，时间复杂度O(logn)。
 * 本题暴力也可解，时间复杂度O(n)，题目也可以用直接判断数组最大值方法。
 **/
class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        int left =0, right = arr.size()-1;

        while (left < right)
        {
            int mid = left + (right - left) / 2;

            if(arr[mid-1] < arr[mid] && arr[mid] < arr[mid+1]){
                left = mid + 1;
            }
            if(arr[mid-1] > arr[mid] && arr[mid] > arr[mid+1]){
                right = mid;
            }
            if(arr[mid-1] < arr[mid] && arr[mid] > arr[mid+1]){
                return mid;
                // break跳出循环减少运行时间
                break;
            }
        }
        return left;
    }
};



/**
 * Solution 2:三分查找
 * 若左等分点大于右等分点，有两种情况：极大值点在左区间或中区间，所以可以排除右区间
 * 若左等分点小于右等分点，有两种情况：极大值点在中区间或右区间，所以可以排除左区间
 **/
class Solution_2 {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        int left =0, right = arr.size()-1;

        while (left < right)
        {
            int m1 = left + (right - left) / 3;
            int m2 = right - (right - left) / 3;
            if(arr[m1] > arr[m2]){
                right = m2 - 1;
            }
            else{
                left = m1 + 1;
            }
        }
        return left;
    }
};


int main(){
    vector<int> arr = {24,69,88,90,99,79,78,67,36,26,19};
    Solution_2 s;
    int result = s.peakIndexInMountainArray(arr);
    cout<<result;
}
